import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-10-05
 * Time: 22:32
 */
public class Solution {
    public static void quickSort(int[] arr) {
        quick(arr,0,arr.length-1);
    }
    //核心操作
    private static void quick(int[] arr,int left,int right) {
        Stack<Integer> stack = new Stack<>();
        int mid = findMid(arr,left,right);

        if (mid > left+1) {
            stack.push(left);
            stack.push(mid-1);
        }

        if (mid < right-1) {
            stack.push(mid+1);
            stack.push(right);
        }

        while (!stack.empty()) {
            right = stack.pop();
            left = stack.pop();
            mid = findMid(arr,left,right);

            if (mid > left+1) {
                stack.push(left);
                stack.push(mid-1);
            }

            if (mid < right-1) {
                stack.push(mid+1);
                stack.push(right);
            }
        }
    }
    //找中点
    private static int findMid(int[] arr,int left,int right) {
        int tmp = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= tmp) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= tmp) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }

    //交换
    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
